ক্রুসকাল অ্যালগরিদম (Kruskal's Algorithm) একটি জনপ্রিয় গ্রাফ অ্যালগরিদম যা একটি সংযোগকারক (Minimum Spanning Tree - MST) তৈরি করতে ব্যবহৃত হয়। এটি একটি অসম্পূর্ণ গ্রাফের মধ্যে ন্যূনতম মোট ওজনের সংযোগকারী তৈরি করে, যা সকল নোডের মধ্যে একটি সংযোগ স্থাপন করে কিন্তু কোনও সাইকেল সৃষ্টি করে না। এই অ্যালগরিদমের মূল উদ্দেশ্য হল, একটি গ্রাফের সমস্ত নোডের মধ্যে সর্বনিম্ন ব্যয়ে সংযোগ স্থাপন করা।
ক্রুসকাল অ্যালগরিদমের কাজের পদ্ধতি
ক্রুসকাল অ্যালগরিদম নিম্নলিখিত ধাপগুলো অনুসরণ করে:
এজগুলি সাজান: গ্রাফের সমস্ত এজকে তাদের ওজনের উপর ভিত্তি করে সাজান, যা ন্যূনতম থেকে সর্বাধিক ওজনের দিকে হয়।
নতুন গ্রাফ তৈরি করুন: একটি খালি গ্রাফ তৈরি করুন যা MST ধারণ করবে।
এজ নির্বাচন: সাজানো এজগুলির মধ্যে থেকে একটি করে এজ নির্বাচন করুন এবং এটি MST-তে যুক্ত করুন, যদি তা সাইকেল সৃষ্টি না করে।
- সাইকেল সৃষ্টির জন্য, ডিস্ক্রিট সেট (disjoint set) বা ইউনিয়ন-ফাইন্ড (Union-Find) ডেটা স্ট্রাকচার ব্যবহার করা হয়।
শেষ করা: MST তে মোট \( V-1 \) (যেখানে \( V \) হল নোডের সংখ্যা) এজ যুক্ত না হওয়া পর্যন্ত পদ্ধতি চালিয়ে যান।
উদাহরণ
ধরা যাক আমাদের একটি গ্রাফ আছে:
1
/ \
2 3
/ \ / \
4---5---6
এডজ ওজনের তালিকা:
- (1, 2, 4)
- (1, 3, 1)
- (2, 4, 3)
- (2, 5, 2)
- (3, 5, 5)
- (5, 6, 6)
ক্রুসকাল অ্যালগরিদম প্রয়োগ:
এজগুলি সাজান (ওজন অনুসারে):
- (1, 3, 1)
- (2, 5, 2)
- (2, 4, 3)
- (1, 2, 4)
- (3, 5, 5)
- (5, 6, 6)
MST তে এজ যুক্ত করতে শুরু করুন:
- (1, 3, 1) যুক্ত করুন (MST = {(1, 3)})
- (2, 5, 2) যুক্ত করুন (MST = {(1, 3), (2, 5)})
- (2, 4, 3) যুক্ত করুন (MST = {(1, 3), (2, 5), (2, 4)})
- (1, 2, 4) যুক্ত করবেন না (এটি সাইকেল সৃষ্টি করে)
- (3, 5, 5) যুক্ত করবেন না (এটি সাইকেল সৃষ্টি করে)
- (5, 6, 6) যুক্ত করুন (MST = {(1, 3), (2, 5), (2, 4), (5, 6)})
পিথনের মাধ্যমে ক্রুসকাল অ্যালগরিদম উদাহরণ:
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal(num_nodes, edges):
ds = DisjointSet(num_nodes)
mst = []
edges.sort(key=lambda x: x[2]) # Sort edges based on weight
for u, v, weight in edges:
if ds.find(u) != ds.find(v):
ds.union(u, v)
mst.append((u, v, weight))
return mst
# ব্যবহার
edges = [
(0, 1, 4),
(0, 2, 1),
(1, 2, 2),
(1, 3, 3),
(2, 3, 5),
(3, 4, 6)
]
mst = kruskal(5, edges)
print("Minimum Spanning Tree:")
for u, v, weight in mst:
print(f"{u} -- {v} == {weight}")
সময় জটিলতা
ক্রুসকাল অ্যালগরিদমের সময় জটিলতা হল:
- O(E log E), যেখানে EE হল গ্রাফের এজের সংখ্যা। এটি মূলত এজগুলিকে সাজানোর জন্য এবং ইউনিয়ন-ফাইন্ড অপারেশনের জন্য ব্যবহৃত হয়।
উপসংহার
ক্রুসকাল অ্যালগরিদম একটি কার্যকরী এবং জনপ্রিয় পদ্ধতি যা একটি গ্রাফের জন্য সর্বনিম্ন স্প্যানিং ট্রি তৈরি করতে ব্যবহৃত হয়। এটি বিভিন্ন প্রয়োগে যেমন নেটওয়ার্ক ডিজাইন, রাস্তা নির্মাণ ইত্যাদিতে গুরুত্বপূর্ণ ভূমিকা পালন করে। এই অ্যালগরিদমের মাধ্যমে আমরা বৃহৎ ডেটাসেটে যুক্ত উপাদানগুলির মধ্যে সর্বনিম্ন ব্যয়ে সংযোগ স্থাপন করতে সক্ষম হই।
